Assuring quality of contemporary software systems is a very challenging taskdue to the often large complexity of the deployment environments in which theywill operate. Service virtualization is an approach to this challenge whereservices within the deployment environment are emulated by synthesising serviceresponse messages from models or by recording and then replaying serviceinteraction messages with the system. Record-and-replay techniques require anapproach where (i) message prototypes can be derived from recorded systeminteractions (i.e. request-response sequences), (ii) a scheme to match incomingrequest messages against message prototypes, and (iii) the synthesis ofresponse messages based on similarities between incoming messages and therecorded system interactions. Previous approaches in service virtualizationhave required a multiple sequence alignment (MSA) algorithm as a means offinding common patterns of similarities and differences between messagesrequired by all three steps. In this paper, we present a novel MSA algorithm based on Generalized SuffixTrees (GSTs). We evaluated the accuracy and efficiency of the proposedalgorithm against six enterprise service message trace datasets, with theproposed algorithm performing up to 50 times faster than standard MSAapproaches. Furthermore, the algorithm has applicability to other domainsbeyond service virtualization.
展开▼
